package leecode.array.数组其他问题;

/**
 * @author wangxi created on 2021/6/13 22:29
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/single-number-iii/
 *
 * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。
 * 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
 */
public class SingleNumberIII {


    public int[] singleNumber(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return new int[0];
        }

        int[] res = new int[2];
        int temp = 0;
        for (int i = 0; i < nums.length; i++) {
            temp ^= nums[i];
        }
        // 定位到temp的哪一位为1，即按照这一位进行分组
        // div表示需要左移几位
        int div = 0;
        while (temp != 0) {
            if ((temp & 1) == 1) {
                break;
            }
            temp = temp >> 1;
            div++;
        }
        int a = 0;
        int b = 0;
        for (int i = 0; i < nums.length; i++) {
            if (((nums[i] >> div) & 1)  != 0) {
                a ^= nums[i];
            } else {
                b ^= nums[i];
            }
        }
        res[0] = a;
        res[1] = b;
        return res;
    }

}
